package data_structure.mooc;

import data_structure.entry.Student;
import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;
import data_structure.helper.SwapArray;

public class InsertionSort {

    private InsertionSort() {

    }

    public static <E extends Comparable<E>> E[] sort2(E[] array) {
        for (int i = array.length - 1; i >= 0; i--) {
            E temp = array[i];
            int j;
            for (j = i; j + 1 <= array.length - 1 && array[j + 1].compareTo (temp) < 0; j++) {
                array[j + 1] = array[j];
            }
            array[j] = temp;
        }
        return array;
    }


    public static <E extends Comparable<E> > void sort2(E[] array,int l,int r) {

        for(int i=l;i<=r;i++){
            E temp=array[i];
            int pre=i;
            for(;pre-1>=l&&array[pre - 1].compareTo (temp)>0;pre--){
                array[pre]=array[pre-1];
            }
            array[pre]=temp;
        }
    }
    public static <E extends Comparable<E>> E[] sort1(E[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i; j - 1 >= 0; j--) {
                if (array[j - 1].compareTo (array[j]) > 0) {
                    SwapArray.swap (array, j - 1, j);
                } else {
                    break;
                }
            }
        }
        return array;
    }

    public static <E extends Comparable<E>> E[] sort3(E[] array) {
        for (int i = 0; i < array.length; i++) {
            //current value
            E temp = array[i];
            //the index of the place where to insert
            int j;
            for (j = i; j - 1 >= 0 && array[j - 1].compareTo (temp) > 0; j--) {
                array[j] = array[j - 1];
            }
            array[j] = temp;
        }
        return array;
    }


}
